#include <bits/stdc++.h>
using namespace std;

/*
3607. 电网维护
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。

这些电站通过 n 条 双向 电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [ui, vi] 表示电站 ui 和电站 vi 之间的连接。直接或间接连接的电站组成了一个 电网 。

最初，所有 电站均处于在线（正常运行）状态。

另给你一个二维数组 queries，其中每个查询属于以下 两种类型之一 ：

[1, x]：请求对电站 x 进行维护检查。如果电站 x 在线，则它自行解决检查。如果电站 x 已离线，则检查由与 x 同一 电网 中 编号最小 的在线电站解决。如果该电网中 不存在 任何 在线 电站，则返回 -1。

[2, x]：电站 x 离线（即变为非运行状态）。

返回一个整数数组，表示按照查询中出现的顺序，所有类型为 [1, x] 的查询结果。

注意：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。

 

示例 1：

输入： c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]

输出： [3,2,3]

解释：



最初，所有电站 {1, 2, 3, 4, 5} 都在线，并组成一个电网。
查询 [1,3]：电站 3 在线，因此维护检查由电站 3 自行解决。
查询 [2,1]：电站 1 离线。剩余在线电站为 {2, 3, 4, 5}。
查询 [1,1]：电站 1 离线，因此检查由电网中编号最小的在线电站解决，即电站 2。
查询 [2,2]：电站 2 离线。剩余在线电站为 {3, 4, 5}。
查询 [1,2]：电站 2 离线，因此检查由电网中编号最小的在线电站解决，即电站 3。
示例 2：

输入： c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]

输出： [1,-1]

解释：

没有连接，因此每个电站是一个独立的电网。
查询 [1,1]：电站 1 在线，且属于其独立电网，因此维护检查由电站 1 自行解决。
查询 [2,1]：电站 1 离线。
查询 [1,1]：电站 1 离线，且其电网中没有其他电站，因此结果为 -1。
 

提示：

1 <= c <= 105
0 <= n == connections.length <= min(105, c * (c - 1) / 2)
connections[i].length == 2
1 <= ui, vi <= c
ui != vi
1 <= queries.length <= 2 * 105
queries[i].length == 2
queries[i][0] 为 1 或 2。
1 <= queries[i][1] <= c
*/

// 法一
class Solution {
public:
    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        vector<int> parent(c + 1);
        vector<bool> online(c + 1, true);
        // root --> sorted set AESC 快速min
        unordered_map<int, set<int>> root_to_online;

        // init 并查集 有序set
        for (int i = 1; i <= c; i++) {
            parent[i] = i;
            root_to_online[i].insert(i);
        }

        // find Func 路径压缩 
        std::function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };

        // 合并
        for (auto& conn : connections) {
            int u = conn[0], v = conn[1];
            int root_u = find(u);
            int root_v = find(v);
            if (root_u == root_v)   continue;   // same 

            // 减少碎片 小集合合并到大集合 减少开销
            if (root_to_online[root_u].size() < root_to_online[root_v].size())  swap(root_u, root_v);

            for (int num : root_to_online[root_v]) {
                root_to_online[root_u].insert(num);
            }
            // 更新parent 
            parent[root_v] = root_u;
            root_to_online.erase(root_v);   // 无效的集合 remove
        }

        // select 
        vector<int> ans;
        for (auto& q : queries) {
            // condition 2
            if (q[0] == 2) {
                int x = q[1];
                if (!online[x]) continue; // 已离线，跳过
                online[x] = false; // 标记离线
                int root = find(x);
                root_to_online[root].erase(x); // 从分量在线集合中删除
            } else {
                int x = q[1];
                int root = find(x);
                auto& online_set = root_to_online[root];
                // 分量无在线电站
                if (online_set.empty()) ans.push_back(-1);
                else if (online[x]) ans.push_back(x);
                else ans.push_back(*online_set.begin());
            }
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    // 并查集 + 逆序 优化
    // helper
    vector<int> parent;    // 并查集父节点（路径压缩）
    vector<int> sz;        // 分量大小（按大小合并优化）
    vector<int> min_online; // 各连通分量的最小在线节点
    static constexpr int INF = numeric_limits<int>::max();

    // 并查集查找（路径压缩，近常数时间）
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    // 并查集合并（小分量合到大分量，维护最小在线节点）
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        min_online[a] = min(min_online[a], min_online[b]);
    }

    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
        int q = queries.size();
        parent.resize(c + 1);
        sz.assign(c + 1, 1);
        min_online.assign(c + 1, INF);
        iota(parent.begin(), parent.end(), 0); // 初始化并查集：parent[i] = i

        // 合并全部
        for (const auto& edge : connections) {
            unite(edge[0], edge[1]);
        }

        // cnt total delete 逆序时用于撤销删除
        vector<int> del_cnt(c + 1, 0);
        for (const auto& qu : queries) {
            if (qu[0] == 2) del_cnt[qu[1]]++;
        }

        // init last 
        for (int i = 1; i <= c; ++i) {
            if (del_cnt[i] == 0) {
                int root = find(i);
                min_online[root] = min(min_online[root], i);
            }
        }

        // 逆序
        vector<int> ans;
        ans.reserve(q); // 预分配空间，避免扩容开销
        for (int i = q - 1; i >= 0; --i) {
            int type = queries[i][0];
            int x = queries[i][1];
            int root = find(x);

            if (type == 1) { // 原查询：查询维护解决者
                if (del_cnt[x] == 0) ans.push_back(x); // x在线，返回自身
                else ans.push_back(min_online[root] == INF ? -1 : min_online[root]); // 取最小在线
            } else { // 原查询：删除x → 逆操作：撤销一次删除
                del_cnt[x]--;
                if (del_cnt[x] == 0) { // 撤销后x在线，更新分量最小在线节点
                    root = find(x);
                    min_online[root] = min(min_online[root], x);
                }
            }
        }

        reverse(ans.begin(), ans.end()); // 恢复原查询顺序
        return ans;
    }
};